<!DOCTYPE html>
            
<HTML>
<HEAD>
<meta name="booktitle" content="Developing Applications With Objective Caml" >
 <meta charset="ISO-8859-1"><meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0">
<META name="GENERATOR" content="hevea 1.05-7 of 2000-02-24">
<META NAME="Author" CONTENT="Christian.Queinnec@lip6.fr">
<LINK rel=stylesheet type="text/css" href="videoc-ocda.css">
<script language="JavaScript" src="videoc.js"><!--
//--></script>
<TITLE>
 Modifiable Data Structures
</TITLE>
</HEAD>
<BODY class="regularBody">
<A HREF="book-ora025.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="index.html"><IMG SRC ="contents_motif.gif" ALT="Contents"></A>
<A HREF="book-ora027.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2> Modifiable Data Structures</H2> 
<A NAME="sec-mutables"></A>
<A NAME="@concepts94"></A>
Values of the following types: vectors, character strings,
records with mutable fields, and references are the data structures whose parts can be
physically modified.<BR>
<BR>
We have seen that an Objective CAML variable bound to a value keeps this value to
the end of its lifetime. You can only modify this binding with a
redefinition---in which case we are not really talking about the ``same''
variable; rather, a new variable of the same name now masks the old
one, which is no longer directly accessible, but which remains unchanged.
With modifiable values, you can change the value associated with a variable
without having to redeclare the latter. You have access to the value of a
variable for writing as well as for reading.<BR>
<BR>
<A NAME="toc31"></A>
<H3> Vectors</H3>
<A NAME="@concepts95"></A>
<A NAME="@concepts96"></A>
<A NAME="@fonctions96"></A>
<A NAME="@fonctions97"></A>Vectors, or one dimensional arrays, collect a known number of elements of
the same type. You can write a vector directly by listing its values
between the symbols <TT>[|</TT> and <TT>|]</TT>, separated by semicolons as
for lists.


<PRE><BR># <B>let</B><CODE> </CODE>v<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>[|</CODE><CODE> </CODE><CODE>3</CODE><CODE>.</CODE><CODE>1</CODE><CODE>4</CODE>;<CODE> </CODE><CODE>6</CODE><CODE>.</CODE><CODE>2</CODE><CODE>8</CODE>;<CODE> </CODE><CODE>9</CODE><CODE>.</CODE><CODE>4</CODE><CODE>2</CODE><CODE> </CODE><CODE>|]</CODE><CODE> </CODE>;;<BR><CODE>val v : float array = [|3.14; 6.28; 9.42|]</CODE><BR>

</PRE>

<A NAME="@fonctions98"></A>
The creation function <TT>Array.create</TT> takes the number of elements in
the vector and an initial value, and returns a new vector.


<PRE><BR># <B>let</B><CODE> </CODE>v<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Array.create<CODE> </CODE><CODE> </CODE><CODE>3</CODE><CODE> </CODE><CODE> </CODE><CODE>3</CODE><CODE>.</CODE><CODE>1</CODE><CODE>4</CODE>;;<BR><CODE>val v : float array = [|3.14; 3.14; 3.14|]</CODE><BR>

</PRE>
<BR>
<BR>
To access or modify a particular element, you give the index of that
element:<A NAME="@fonctions99"></A> 


<H3> Syntax </H3> <HR>

 <I>expr</I><SUB><I><FONT SIZE=2>1</FONT></I></SUB> <B>.</B> <B>(</B> <I>expr</I><SUB><I><FONT SIZE=2>2</FONT></I></SUB> <B>)</B>


<HR>




<H3> Syntax </H3> <HR>

 <I>expr</I><SUB><I><FONT SIZE=2>1</FONT></I></SUB> <B>.</B> <B>(</B> <I>expr</I><SUB><I><FONT SIZE=2>2</FONT></I></SUB> <B>)</B> 
 <B>&lt;-</B> <I>expr</I><SUB><I><FONT SIZE=2>3</FONT></I></SUB> 


<HR>

<BR>
<BR>
<I>expr</I><SUB><I><FONT SIZE=2>1</FONT></I></SUB> should be a vector (type <I>array</I>)
whose values have type <I>expr</I><SUB><I><FONT SIZE=2>3</FONT></I></SUB>. The expression
<I>expr</I><SUB><I><FONT SIZE=2>2</FONT></I></SUB> must, of course, have type <I>int</I>. The modification
is an expression of type <I>unit</I>. The first element of a vector has
index 0 and the index of the last element is the length of the vector minus
1. The parentheses around the index expression are required.<BR>
<BR>


<PRE><BR># v<CODE>.</CODE><TT>(</TT><CODE>1</CODE><TT>)</TT><CODE> </CODE>;;<BR><CODE>- : float = 3.14</CODE><BR># v<CODE>.</CODE><TT>(</TT><CODE>0</CODE><TT>)</TT><CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE><CODE>1</CODE><CODE>0</CODE><CODE>0</CODE><CODE>.</CODE><CODE>0</CODE><CODE> </CODE>;;<BR><CODE>- : unit = ()</CODE><BR># v<CODE> </CODE>;;<BR><CODE>- : float array = [|100; 3.14; 3.14|]</CODE><BR>

</PRE>
<BR>
<BR>
If the index used to access an element in an array is outside the range of
indices of the array, an exception is raised at the moment of access.


<PRE><BR># v<CODE>.</CODE><TT>(</TT><CODE>-</CODE><CODE>1</CODE><TT>)</TT><CODE> </CODE><CODE>+.</CODE><CODE> </CODE><CODE>4</CODE><CODE>.</CODE><CODE>0</CODE>;;<BR><CODE>Uncaught exception: Invalid_argument("Array.get")</CODE><BR>

</PRE>

This check is done during program execution, which can slow it down.
Nevertheless it is essential, in order to avoid writing to
memory outside the space allocated to a vector, which would cause serious
execution errors.<BR>
<BR>
The functions for manipulating arrays are part of the <TT>Array</TT> module
in the standard library. We'll describe them in chapter
<A HREF="index.html#chap-Bibliotheques">8</A> (page <A HREF="book-ora076.html#sec-mod-array">??</A>). In the examples
below, we will use the following three functions from the <TT>Array</TT>
module:<BR>
<BR>
<UL>
<LI>
 <TT>create</TT> which creates an array of the given size with the
 given initial value;

<LI> <TT>length</TT> which gives the length of a vector;

<LI> <TT>append</TT> which concatenates two vectors.
</UL>
<H4> Sharing of Values in a Vector</H4>
<A NAME="@concepts97"></A>
All the elements of a vector contain the value that was passed in when it
was created. This implies a sharing of this value, if it is a structured
value. For example, let's create a matrix as a vector of vectors using the
function <TT>create</TT> from the <TT>Array</TT> module.


<PRE><BR># <B>let</B><CODE> </CODE>v<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Array.create<CODE> </CODE><CODE>3</CODE><CODE> </CODE><CODE>0</CODE>;;<BR><CODE>val v : int array = [|0; 0; 0|]</CODE><BR># <B>let</B><CODE> </CODE>m<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Array.create<CODE> </CODE><CODE>3</CODE><CODE> </CODE>v;;<BR><CODE>val m : int array array = [|[|0; 0; 0|]; [|0; 0; 0|]; [|0; 0; 0|]|]</CODE><BR>

</PRE>
 <BR>
<BR>
<BLOCKQUOTE><DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV>
<DIV ALIGN=center>
<IMG SRC="book-ora004.gif">
<BR>
<BR>
<DIV ALIGN=center>Figure 3.1: Memory representation of a vector sharing its elements.</DIV><BR>

<A NAME="fig-vecteur1"></A>
</DIV>
<DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>If you modify one of the fields of vector <TT>v</TT>, which was used in the
creation of <TT>m</TT>, then you automatically modify all the ``rows''
of the matrix together (see figures <A HREF="book-ora026.html#fig-vecteur1">3.1</A> and
<A HREF="book-ora026.html#fig-vecteur2">3.2</A>).


<PRE><BR># v<CODE>.</CODE><TT>(</TT><CODE>0</CODE><TT>)</TT><CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE><CODE>1</CODE>;;<BR><CODE>- : unit = ()</CODE><BR># m;;<BR><CODE>- : int array array = [|[|1; 0; 0|]; [|1; 0; 0|]; [|1; 0; 0|]|]</CODE><BR>

</PRE>
<BR>
<BR>
<BLOCKQUOTE><DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV>
<DIV ALIGN=center>
<IMG SRC="book-ora005.gif">
<BR>
<BR>
<DIV ALIGN=center>Figure 3.2: Modification of shared elements of a vector.</DIV><BR>

<A NAME="fig-vecteur2"></A>
</DIV>
<DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>Duplication occurs if the initialization value of the vector (the second
argument passed to <TT>Array.create</TT>) is an atomic value
and there is sharing if this value is a structured value.<BR>
<BR>
<A NAME="@concepts98"></A><A NAME="@concepts99"></A>Values whose size does not exceed the standard size of Objective CAML
values---that is, the memory word---are called atomic values. These are
the integers, characters, booleans, and constant constructors. The other
values---structured values---are represented by a pointer into a memory area.
This distinction is detailed in chapter <A HREF="index.html#chap-GC">9</A> (page
<A HREF="index.html#chap-GC">??</A>).<BR>Vectors of floats are a special case. Although floats are structured
values, the creation of a vector of floats causes the the initial value to
be copied. This is for reasons of optimization. Chapter <A HREF="index.html#chap-IC">12</A>, on
the interface with the C language (page <A HREF="index.html#chap-IC">??</A>), describes this
special case.<BR>
<BR>

<H4> Non-Rectangular Matrices</H4>
A matrix, a vector of vectors, does not need not to be rectangular. In fact, 
nothing stops you from replacing one of the vector elements with a vector of a
different length. This is useful to limit the size of such a matrix. The
following value <TT>t</TT> constructs a triangular matrix for the
coefficients of Pascal's triangle.


<PRE><BR># <B>let</B><CODE> </CODE>t<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>[|</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>[|</CODE><CODE>1</CODE><CODE>|]</CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>[|</CODE><CODE>1</CODE>;<CODE> </CODE><CODE>1</CODE><CODE>|]</CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>[|</CODE><CODE>1</CODE>;<CODE> </CODE><CODE>2</CODE>;<CODE> </CODE><CODE>1</CODE><CODE>|]</CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>[|</CODE><CODE>1</CODE>;<CODE> </CODE><CODE>3</CODE>;<CODE> </CODE><CODE>3</CODE>;<CODE> </CODE><CODE>1</CODE><CODE>|]</CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>[|</CODE><CODE>1</CODE>;<CODE> </CODE><CODE>4</CODE>;<CODE> </CODE><CODE>6</CODE>;<CODE> </CODE><CODE>4</CODE>;<CODE> </CODE><CODE>1</CODE><CODE>|]</CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>[|</CODE><CODE>1</CODE>;<CODE> </CODE><CODE>5</CODE>;<CODE> </CODE><CODE>1</CODE><CODE>0</CODE>;<CODE> </CODE><CODE>1</CODE><CODE>0</CODE>;<CODE> </CODE><CODE>5</CODE>;<CODE> </CODE><CODE>1</CODE><CODE>|]</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|]</CODE><CODE> </CODE>;;<BR><CODE>val t : int array array =</CODE><BR><CODE>  [|[|1|]; [|1; 1|]; [|1; 2; 1|]; [|1; 3; 3; 1|]; [|1; 4; 6; 4; ...|]; ...|]</CODE><BR># t<CODE>.</CODE><TT>(</TT><CODE>3</CODE><TT>)</TT><CODE> </CODE>;;<BR><CODE>- : int array = [|1; 3; 3; 1|]</CODE><BR>

</PRE>

In this example, the element of vector <TT>t</TT> with index <I>i</I> is a
vector of integers with size <I>i</I>+1. To manipulate such matrices, you have
to calculate the size of each element vector.<BR>
<BR>

<H4> Copying Vectors</H4>
When you copy a vector, or when you concatenate two vectors, the result
obtained is a new vector. A modification of the original vectors does not
result in the modification of the copies, unless, as usual, there are
shared values.


<PRE><BR># <B>let</B><CODE> </CODE>v2<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Array.copy<CODE> </CODE>v<CODE> </CODE>;;<BR><CODE>val v2 : int array = [|1; 0; 0|]</CODE><BR># <B>let</B><CODE> </CODE>m2<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Array.copy<CODE> </CODE>m<CODE> </CODE>;;<BR><CODE>val m2 : int array array = [|[|1; 0; 0|]; [|1; 0; 0|]; [|1; 0; 0|]|]</CODE><BR># v<CODE>.</CODE><TT>(</TT><CODE>1</CODE><TT>)</TT><CODE>&lt;-</CODE><CODE> </CODE><CODE>3</CODE><CODE>5</CODE><CODE>2</CODE>;;<BR><CODE>- : unit = ()</CODE><BR># v2;;<CODE> </CODE><BR><CODE>- : int array = [|1; 0; 0|]</CODE><BR># m2<CODE> </CODE>;;<BR><CODE>- : int array array = [|[|1; 352; 0|]; [|1; 352; 0|]; [|1; 352; 0|]|]</CODE><BR>

</PRE>

We notice in this example that copying <TT>m</TT> only copies the pointers
to <TT>v</TT>. If one of the elements of <TT>v</TT> is modified,
<TT>m2</TT> is modified too. <BR>
<BR>
Concatenation creates a new vector whose size
is equal to the sum of the sizes of the two others.


<PRE><BR># <B>let</B><CODE> </CODE>mm<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Array.append<CODE> </CODE>m<CODE> </CODE>m<CODE> </CODE>;;<BR><CODE>val mm : int array array =</CODE><BR><CODE>  [|[|1; 352; 0|]; [|1; 352; 0|]; [|1; 352; 0|]; [|1; 352; 0|];</CODE><BR><CODE>    [|1; 352; ...|]; ...|]</CODE><BR># Array.length<CODE> </CODE>mm<CODE> </CODE>;;<BR><CODE>- : int = 6</CODE><BR># m<CODE>.</CODE><TT>(</TT><CODE>0</CODE><TT>)</TT><CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE>Array.create<CODE> </CODE><CODE>3</CODE><CODE> </CODE><CODE>0</CODE><CODE> </CODE>;;<BR><CODE>- : unit = ()</CODE><BR># m<CODE> </CODE>;;<BR><CODE>- : int array array = [|[|0; 0; 0|]; [|1; 352; 0|]; [|1; 352; 0|]|]</CODE><BR># mm<CODE> </CODE>;;<BR><CODE>- : int array array =</CODE><BR><CODE>[|[|1; 352; 0|]; [|1; 352; 0|]; [|1; 352; 0|]; [|1; 352; 0|];</CODE><BR><CODE>  [|1; 352; ...|]; ...|]</CODE><BR>

</PRE>
<BR>
<BR>
On the other hand, modification of <TT>v</TT>, a value shared by <TT>m</TT>
and <TT>mm</TT>, does affect both these matrices.


<PRE><BR># v<CODE>.</CODE><TT>(</TT><CODE>1</CODE><TT>)</TT><CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE><CODE>1</CODE><CODE>8</CODE><CODE> </CODE>;;<BR><CODE>- : unit = ()</CODE><BR># mm;;<BR><CODE>- : int array array =</CODE><BR><CODE>[|[|1; 18; 0|]; [|1; 18; 0|]; [|1; 18; 0|]; [|1; 18; 0|]; [|1; 18; ...|];</CODE><BR><CODE>  ...|]</CODE><BR>

</PRE>
<BR>
<BR>
<A NAME="toc32"></A>
<H3> Character Strings</H3>
<A NAME="sub-PIstr"></A>
<A NAME="@concepts100"></A>
Character strings can be considered a special case of vectors of
characters. Nevertheless, for efficient memory usage<A NAME="text12" HREF="book-ora034.html#note12"><SUP><FONT SIZE=2>1</FONT></SUP></A> their type is
specialized. Moreover, access to their elements has a special syntax:


<H3> Syntax </H3> <HR>

 <I>expr</I><SUB><I><FONT SIZE=2>1</FONT></I></SUB> <B>.</B> <B>[</B><I>expr</I><SUB><I><FONT SIZE=2>2</FONT></I></SUB><B>]</B> 


<HR>


The elements of a character string can be physically modified:<A NAME="@fonctions100"></A>


<H3> Syntax </H3> <HR>


 <I>expr</I><SUB><I><FONT SIZE=2>1</FONT></I></SUB> <B>.</B> <B>[</B><I>expr</I><SUB><I><FONT SIZE=2>2</FONT></I></SUB><B>]</B> 
 <B>&lt;-</B> <I>expr</I><SUB><I><FONT SIZE=2>3</FONT></I></SUB>



<HR>

<BR>
<BR>


<PRE><BR># <B>let</B><CODE> </CODE>s<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>"hello"</CODE>;;<BR><CODE>val s : string = "hello"</CODE><BR># s<CODE>.[</CODE><CODE>2</CODE><CODE>]</CODE>;;<BR><CODE>- : char = 'l'</CODE><BR># s<CODE>.[</CODE><CODE>2</CODE><CODE>]&lt;-</CODE><CODE>'Z'</CODE>;;<BR><CODE>- : unit = ()</CODE><BR># s;;<BR><CODE>- : string = "heZlo"</CODE><BR>

</PRE>
<BR>
<BR>
<A NAME="toc33"></A>
<H3> Mutable Fields of Records</H3>
<A NAME="@concepts101"></A>
<A NAME="@fonctions101"></A>
Fields of a record can be declared mutable. All you have to do is to show
this in the declaration of the type of the record using the keyword
<B>mutable</B>. 


<H3> Syntax </H3> <HR>


<B>type</B> <I>name</I> <B>=</B> <B>{</B> ...<B>;</B>
 <B>mutable</B> <I>name</I><SUB><I><FONT SIZE=2><I>i</I></FONT></I></SUB> <B>:</B> <I>t</I> 
 <B>;</B> ...<B>}</B>



<HR>

<BR>
<BR>
Here is a small example defining a record type for points in the plane:


<PRE><BR># <B>type</B><CODE> </CODE>point<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE><B>mutable</B><CODE> </CODE>xc<CODE> </CODE><CODE>:</CODE><CODE> </CODE>float;<CODE> </CODE><B>mutable</B><CODE> </CODE>yc<CODE> </CODE><CODE>:</CODE><CODE> </CODE>float<CODE> </CODE>}<CODE> </CODE>;;<BR><CODE>type point = { mutable xc: float; mutable yc: float }</CODE><BR># <B>let</B><CODE> </CODE>p<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE>xc<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>1</CODE><CODE>.</CODE><CODE>0</CODE>;<CODE> </CODE>yc<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>0</CODE><CODE>.</CODE><CODE>0</CODE><CODE> </CODE>}<CODE> </CODE>;;<BR><CODE>val p : point = {xc=1; yc=0}</CODE><BR>

</PRE>
<BR>
<BR>
Thus the value of a field which is declared <B>mutable</B> can be modified
using the syntax:<A NAME="@fonctions102"></A>


<H3> Syntax </H3> <HR>


 <I>expr</I><SUB><I><FONT SIZE=2>1</FONT></I></SUB> <B>.</B> <I>name</I> <B>&lt;-</B> <I>expr</I><SUB><I><FONT SIZE=2>2</FONT></I></SUB> 



<HR>

<BR>
<BR>
The expression <I>expr</I><SUB><I><FONT SIZE=2>1</FONT></I></SUB> should be a record type which has the field
<I>name</I>. The modification operator returns a value of type
<I>unit</I>. 


<PRE><BR># p<CODE>.</CODE>xc<CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE><CODE>3</CODE><CODE>.</CODE><CODE>0</CODE><CODE> </CODE>;;<BR><CODE>- : unit = ()</CODE><BR># p<CODE> </CODE>;;<BR><CODE>- : point = {xc=3; yc=0}</CODE><BR>

</PRE>
<BR>
<BR>
We can write a function for moving a point by modifying its components. 
We use a local declaration with pattern matching in order to sequence the
side-effects. 


<PRE><BR># <B>let</B><CODE> </CODE>moveto<CODE> </CODE>p<CODE> </CODE>dx<CODE> </CODE>dy<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>()<CODE> </CODE><CODE>=</CODE><CODE> </CODE>p<CODE>.</CODE>xc<CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE>p<CODE>.</CODE>xc<CODE> </CODE><CODE>+.</CODE><CODE> </CODE>dx<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE>p<CODE>.</CODE>yc<CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE>p<CODE>.</CODE>yc<CODE> </CODE><CODE>+.</CODE><CODE> </CODE>dy<CODE> </CODE>;;<BR><CODE>val moveto : point -&gt; float -&gt; float -&gt; unit = &lt;fun&gt;</CODE><BR># moveto<CODE> </CODE>p<CODE> </CODE><CODE>1</CODE><CODE>.</CODE><CODE>1</CODE><CODE> </CODE><CODE>2</CODE><CODE>.</CODE><CODE>2</CODE><CODE> </CODE>;;<BR><CODE>- : unit = ()</CODE><BR># p<CODE> </CODE>;;<BR><CODE>- : point = {xc=4.1; yc=2.2}</CODE><BR>

</PRE>
<BR>
<BR>
It is possible to mix mutable and non-mutable fields in the definition of a
record. Only those specified as <B>mutable</B> may be modified.


<PRE><BR># <B>type</B><CODE> </CODE>t<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE>c1<CODE> </CODE><CODE>:</CODE><CODE> </CODE>int;<CODE> </CODE><B>mutable</B><CODE> </CODE>c2<CODE> </CODE><CODE>:</CODE><CODE> </CODE>int<CODE> </CODE>}<CODE> </CODE>;;<BR><CODE>type t = { c1: int; mutable c2: int }</CODE><BR># <B>let</B><CODE> </CODE>r<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE>c1<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>0</CODE>;<CODE> </CODE>c2<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>0</CODE><CODE> </CODE>}<CODE> </CODE>;;<BR><CODE>val r : t = {c1=0; c2=0}</CODE><BR># r<CODE>.</CODE>c1<CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE><CODE>1</CODE><CODE> </CODE>;;<BR><CODE>Characters 0-9:</CODE><BR><CODE>The label c1 is not mutable</CODE><BR># r<CODE>.</CODE>c2<CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE><CODE>1</CODE><CODE> </CODE>;;<BR><CODE>- : unit = ()</CODE><BR># r<CODE> </CODE>;;<BR><CODE>- : t = {c1=0; c2=1}</CODE><BR>

</PRE>
<BR>
<BR>
On page <A HREF="book-ora028.html#ex-pile">??</A> we give an example of using records with
modifiable fields and arrays to implement a stack structure.<BR>
<BR>
<A NAME="toc34"></A>
<H3> References</H3>
<A NAME="@fonctions103"></A>
<A NAME="@concepts102"></A>
<A NAME="@concepts103"></A>
Objective CAML provides a polymorphic type <TT>ref</TT> which can be seen
as the type of a pointer to any value; in Objective CAML terminology we call it
a reference to a value. A referenced value can be
modified. The type <I>ref</I> is defined as a record with one
modifiable field:<BR>
<BR>
<PRE>
type 'a ref = {mutable contents:'a}
</PRE>This type is provided as a syntactic shortcut. We
construct a reference to a value using the function <TT>ref</TT>. The
referenced value can be reached using the prefix function
<B>(!)</B>. The function modifying the content of a reference is the
infix function <B>(:=)</B>.
<A NAME="@concepts104"></A><A NAME="@fonctions104"></A>
<A NAME="@fonctions105"></A>


<PRE><BR># <B>let</B><CODE> </CODE>x<CODE> </CODE><CODE>=</CODE><CODE> </CODE>ref<CODE> </CODE><CODE>3</CODE><CODE> </CODE>;;<CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><BR><CODE>val x : int ref = {contents=3}</CODE><BR># x<CODE> </CODE>;;<BR><CODE>- : int ref = {contents=3}</CODE><BR># <CODE>!</CODE>x<CODE> </CODE>;;<CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><BR><CODE>- : int = 3</CODE><BR># x<CODE> </CODE><CODE>:=</CODE><CODE> </CODE><CODE>4</CODE><CODE> </CODE>;;<CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><BR><CODE>- : unit = ()</CODE><BR># <CODE>!</CODE>x<CODE> </CODE>;;<BR><CODE>- : int = 4</CODE><BR># x<CODE> </CODE><CODE>:=</CODE><CODE> </CODE><CODE>!</CODE>x<CODE>+</CODE><CODE>1</CODE><CODE> </CODE>;;<BR><CODE>- : unit = ()</CODE><BR># <CODE>!</CODE>x<CODE> </CODE>;;<BR><CODE>- : int = 5</CODE><BR>

</PRE>
<BR>
<BR>
<A NAME="toc35"></A>
<H3> Polymorphism and Modifiable Values</H3>
<A NAME="pi-weak-type-var"></A>
The type <I>ref</I> is parameterized. This is what lets us use it to
create references to values of any type whatever. However, it is
necessary to place certain restrictions on the type of referenced
values; we cannot allow the creation of a reference to a value with a
polymorphic type without taking some precautions.<BR>
<BR>
Let us suppose that there were no restriction; then someone could
declare:
<PRE>
let x = ref [] ;;
</PRE>Then the variable <TT>x</TT> would have type <I>'a list ref</I> and
its value could be modified in a way which would be inconsistent with
the strong static typing of Objective CAML:


<PRE><BR>x<CODE> </CODE><CODE>:=</CODE><CODE> </CODE><CODE>1</CODE><CODE> </CODE>::<CODE> </CODE><CODE>!</CODE>x<CODE> </CODE>;;<CODE> </CODE><BR>x<CODE> </CODE><CODE>:=</CODE><CODE> </CODE><B>true</B><CODE> </CODE>::<CODE> </CODE><CODE>!</CODE>x<CODE> </CODE>;;<BR>

</PRE>

Thus we would have one and the same variable having type <I>int
 list</I> at one moment and <I>bool list</I> the next.<BR>
<BR>
In order to avoid such a situation, Objective CAML's type inference
mechanism uses a new category of type variables: weak type
variables. Syntactically, they are distinguished by the underscore
character which prefixes them.


<PRE><BR># <B>let</B><CODE> </CODE>x<CODE> </CODE><CODE>=</CODE><CODE> </CODE>ref<CODE> </CODE>[]<CODE> </CODE>;;<BR><CODE>val x : '_a list ref = {contents=[]}</CODE><BR>

</PRE>

<A NAME="@concepts105"></A>
The type variable <I>'_a</I> is not a type parameter, but an unknown
type awaiting instantiation; the first use of <TT>x</TT> after its
declaration fixes the value that <I>'_a</I> will take in all
types that depend on it, permanently.


<PRE><BR># x<CODE> </CODE><CODE>:=</CODE><CODE> </CODE><CODE>0</CODE><CODE>::!</CODE>x<CODE> </CODE>;;<BR><CODE>- : unit = ()</CODE><BR># x<CODE> </CODE>;;<BR><CODE>- : int list ref = {contents=[0]}</CODE><BR>

</PRE>

From here onward, the variable <TT>x</TT> has type <I>int list
ref</I>. <BR>
<BR>
A type containing an unknown is in fact monomorphic even though its
type has not been specified. It is not possible to instantiate this
unknown with a polymorphic type.<BR>
<BR>


<PRE><BR># <B>let</B><CODE> </CODE>x<CODE> </CODE><CODE>=</CODE><CODE> </CODE>ref<CODE> </CODE>[]<CODE> </CODE>;;<BR><CODE>val x : '_a list ref = {contents=[]}</CODE><BR># x<CODE> </CODE><CODE>:=</CODE><CODE> </CODE><TT>(</TT><B>function</B><CODE> </CODE>y<CODE> </CODE>-&gt;<CODE> </CODE>()<TT>)</TT><CODE>::!</CODE>x<CODE> </CODE>;;<BR><CODE>- : unit = ()</CODE><BR># x<CODE> </CODE>;;<BR><CODE>- : ('_a -&gt; unit) list ref = {contents=[&lt;fun&gt;]}</CODE><BR>

</PRE>

In this example, even though we have instantiated the unknown type
with a type which is a priori polymorphic (<I>'a -&gt;
unit</I>), the type has remained monomorphic with a new unknown type.<BR>
<BR>
This restriction of polymorphism applies not only to references, but
to any value containing a modifiable part: vectors, records having at
least one field declared <B>mutable</B>, etc. Thus all the type
parameters, even those which have nothing to do with a modifiable
part, are weak type variables.


<PRE><BR># <B>type</B><CODE> </CODE><TT>(</TT><I>'a</I><CODE>,</CODE><I>'b</I><TT>)</TT><CODE> </CODE>t<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE>ch1<CODE> </CODE><CODE>:</CODE><I>'a</I><CODE> </CODE>list<CODE> </CODE>;<CODE> </CODE><B>mutable</B><CODE> </CODE>ch2<CODE> </CODE><CODE>:</CODE><CODE> </CODE><I>'b</I><CODE> </CODE>list<CODE> </CODE>}<CODE> </CODE>;;<BR><CODE>type ('a, 'b) t = { ch1: 'a list; mutable ch2: 'b list }</CODE><BR># <B>let</B><CODE> </CODE>x<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE>ch1<CODE> </CODE><CODE>=</CODE><CODE> </CODE>[]<CODE> </CODE>;<CODE> </CODE>ch2<CODE> </CODE><CODE>=</CODE><CODE> </CODE>[]<CODE> </CODE>}<CODE> </CODE>;;<BR><CODE>val x : ('_a, '_b) t = {ch1=[]; ch2=[]}</CODE><BR>

</PRE>
<BR>
<BR>


<H3> Warning </H3> <HR>

This modification of the typing of application has consequences for
pure functional programs.


<HR>

<BR>
<BR>
Likewise, when you apply a polymorphic value to a polymorphic function,
you get a weak type variable, because you must not exclude the
possibility that the function may construct physically modifiable
values. In other words, the result of the application is always
monomorphic. 


<PRE><BR># <CODE> </CODE><TT>(</TT><B>function</B><CODE> </CODE>x<CODE> </CODE>-&gt;<CODE> </CODE>x<TT>)</TT><CODE> </CODE>[]<CODE> </CODE><CODE> </CODE>;;<BR><CODE>- : '_a list = []</CODE><BR>

</PRE>
<BR>
<BR>
You get the same result with partial application:


<PRE><BR># <B>let</B><CODE> </CODE>f<CODE> </CODE>a<CODE> </CODE>b<CODE> </CODE><CODE>=</CODE><CODE> </CODE>a<CODE> </CODE>;;<BR><CODE>val f : 'a -&gt; 'b -&gt; 'a = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE>g<CODE> </CODE><CODE>=</CODE><CODE> </CODE>f<CODE> </CODE><CODE>1</CODE><CODE> </CODE>;;<BR><CODE>val g : '_a -&gt; int = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
To get a polymorphic type back, you have to abstract the second
argument of <TT>f</TT> and then apply it:


<PRE><BR># <B>let</B><CODE> </CODE>h<CODE> </CODE>x<CODE> </CODE><CODE>=</CODE><CODE> </CODE>f<CODE> </CODE><CODE>1</CODE><CODE> </CODE>x<CODE> </CODE>;;<BR><CODE>val h : 'a -&gt; int = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
In effect, the expression which defines <TT>h</TT> is the functional
expression <B>function</B><CODE> </CODE>x<CODE> </CODE>-&gt;<CODE> </CODE>f<CODE> </CODE><CODE>1</CODE><CODE> </CODE>x. Its evaluation produces a
closure which does not risk producing a side effect, because the body
of the function is not evaluated.<BR>
<BR>
In general, we distinguish so-called ``non-expansive'' expressions,
whose calculation we are sure carries no risk of causing a side effect,
from other expressions, called ``expansive.'' Objective CAML's type system
classifies expressions of the language according to their
syntactic form:
<UL>
<LI>
 ``non-expansive'' expressions include primarily 
variables, constructors of non-mutable values, and
abstractions;

<LI> ``expansive'' expressions include primarily
applications and constructors of modifiable values. We can also include
here control structures like conditionals and pattern matching.
</UL> <HR>
<A HREF="book-ora025.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="index.html"><IMG SRC ="contents_motif.gif" ALT="Contents"></A>
<A HREF="book-ora027.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
